/**
 * 
 */
package tree.passed;

/**
 * @author xyyi
 *
 */
public class FlattenBinaryTreeToLinkedList {

	/**
	Given a binary tree, flatten it to a linked list in-place.

	For example,
	Given

	     1
	    / \
	   2   5
	  / \   \
	 3   4   6

	The flattened tree should look like:

	1
	\
	 2
	  \
	   3
	    \
	     4
	      \
	       5
	        \
	         6
	         
	 Recursion
	[解题思路]
	递归解法。对于任一节点，flatten右树，然后节点插入左树最左边，成为新的头节点。flatten右树，右树最左边接上新链表的最右节点。
	 */
	// best
	public TreeNode flatten(TreeNode root) {
		if (root == null || (root.left == null && root.right == null))
			return root;

		TreeNode right = convertToLink(root.right);
		TreeNode left = convertToLink(root.left);

		root.right = left;
		root.left = null;
		TreeNode node = root;
		while (node.right != null) {
			node = node.right;
		}
		node.right = right;

		return root;
	}

	public void flatten1(TreeNode root) {
		if (root == null)
			return;

		convertToLink(root);
	}

	private TreeNode convertToLink(TreeNode root) {
		if (root.left == null && root.right == null)
			return root;

		TreeNode right = null;
		if (root.right != null) {
			right = convertToLink(root.right);
		}

		TreeNode node = root;
		TreeNode left = null;
		if (root.left != null) {
			left = convertToLink(root.left);
			root.right = left;
			root.left = null;
			while (node.right != null)
				node = node.right;
		}

		if (right != null) {
			node.right = right;
		}

		return root;
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public FlattenBinaryTreeToLinkedList() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
